package com.hsc.offer;

import java.util.ArrayList;

/**
 * @author
 * @date 2025-07-01
 * @Description 19.输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
 * // 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
 * 例如，如果输入如下4 X 4矩阵：
 * 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
 * ==:矩阵(相当于一个房间的网格地板）
 * 1  2  3    4
 * 5  6  7    8
 * 9  10 11   12
 * 13 14 15   16
 * 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
 * 矩阵遍历过程 = 机器人扫地
 * 矩阵：相当于一个房间的网格地板。
 * 机器人：从左上角出发，按照固定方向（右→下→左→上）移动。
 * 方向数组：如同机器人的导航系统，预先设定了四个方向。
 * 标记元素：机器人走过的地方会 “撒上灰尘”（标记为Integer.MAX_VALUE），避免重复清扫。
 * 转向逻辑：当机器人遇到墙壁（矩阵边界）或已撒过灰尘的区域时，自动右转（改变方向）。
 * 方向控制 = 方向盘
 * num 相当于方向盘的角度，每转 90 度（num++）改变一次方向。
 * num % 4 确保方向盘只能在 0°、90°、180°、270° 四个位置切换，对应右、下、左、上四个方向
 */
public class OfferTest14 {
    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        System.out.println("printMatrix(matrix) = " + printMatrix(matrix));
    }


    public static ArrayList<Integer> printMatrix(int[][] matrix) {
        // 控制当前方向索引 相当于 “方向盘”
        int num = 0;
        // 定义当前位置的坐标 相当于当前的指针
        // 定义行
        int row = 0;
        // 定义列
        int col = 0;
        // 定义方向数组：包含上下左右四个方向的坐标变化 相当于“导航地图”
        // {行,列}
        // 四个方向：{0,1} {1，0} {0，-1} {-1,0}
        int[][] toward = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 定义结果 收集
        ArrayList<Integer> result = new ArrayList<>();
        // 循环将当前位置添加到结果集 并且标记当前位置为已经处理过
        while (true) {
            // 将当前位置添加到结果集中
            result.add(matrix[row][col]);
            System.out.println(matrix[row][col]);
            // 将当前位置（指针的）元素进行标记
            matrix[row][col] = Integer.MAX_VALUE;
            // 判断是否所有的元素都已经遍历过了 如果遍历过了就退出 数组的所有的元素数量：行(matrix.length）* 列(matrix[0].length)
            if (result.size() >= matrix.length * matrix[0].length) {
                break;
            }
            // 计算下一个位置 （行,列）
            // 行位置计算
            // num % 4 确保方向索引在 0-3 之间循环（右→下→左→上）。因为我们这里是  4 X 4 矩阵的矩阵
            int nextRow = row + toward[num % 4][0];
            // 列位置计算
            int nextCol = col + toward[num % 4][1];
            // 判断当前位置是否满足条件
            // 第一个条件 如果下一个位置的行小于0 了 换方向（num++） 比如：从下往上 行数递减
            // 第二个条件 如果下一个位置的列小于0 了 换方向（num++） 比如：从右往左 列数递减
            // 第三个条件 如果下一个位置的行坐标大于矩阵最大行了 换方向（num++）
            // 第四个条件 如果下一个位置的列坐标大于矩阵最大列了  换方向（num++）
            // 第五个条件 如果下一个位置的元素碰到了标记过的位置 说明重复的元素了 换方向（num++） =》matrix[nextRow][nextCol] == Integer.MAX_VALUE)
            if (nextRow < 0 || nextCol < 0 || nextRow >= matrix.length || nextCol >= matrix[0].length || matrix[nextRow][nextCol] == Integer.MAX_VALUE) {
                // 1、nextCol >= matrix[0].length ： 第一次换方向的情况 下一列等于二维数组的列长度（从左到右结束)  方向开始 从下往上
                // 2、nextRow >= matrix.length  : 第二次换方向 从右往左 当从上往下时，下一个位置的行位置大于数组的长度时，说明需要换方向了。
                // 3、nextCol < 0 : 第三次换方向。当从右到左，进行计算时，下一个位置的列小于 0，说明要换方向了，要从下往上了
                // 4、matrix[nextRow][nextCol] == Integer.MAX_VALUE : 第四次换方向。当从下到上时，下一个位置为 [0][0]，=>二位数组最开始的位置就是 [0][0],然而这个位置已经被做过标记了（最开始循环的时候），所以当计算下一个为这个时，碰碰到了重复的元素，要换方向了
                // 5、matrix[1][3] == Integer.MAX_VALUE：第五次换方向，这个元素在之前已经做过标记，已经遍历过了，碰到了重复的元素，开始要从上往下了。 6、第六次换方向 matrix[3][2]= Integer.MAX_VALUE 这个元素在之前已经做过标记，已经遍历过了，碰到了重复的元素，开始要从右往左
                num++;
            }

            // 上面是计算 ，这里是实际 获取下一个数值的坐标（行,列）这里有两种情况
            // 1、num 没变 没有换方向
            // 2、num ++  换方向了
            // 计算当前方向的下一个位置的（行，列）
            // 当被除数小于除数时，结果即为被除数本身（如 0%4 1%4、2%4、3%4）
            // num % 4 ：num % 4 确保方向索引在 0-3 之间循环（右→下→左→上）
            row = row + toward[num % 4][0];
            col = col + toward[num % 4][1];

        }
        // 返回收集的计算
        return result;
    }
}
